In database applications associated with text or speech recognition (e.g., text typed in, or speech uttered by, a user), the ability to quickly find records that match a user's query is of critical importance. For example, a database record might include a customer's first, middle and last name, address, phone number, and the last amount spent. The user of a database will in general want to retrieve records that match some query, for example, “John Doe,” “John Doe on North Street,” and so forth. When the queries are constrained to be simple, for example “Address=1412 Main Street”, and exact matches are adequate, hashing techniques allow for fast database access.
The problem is significantly more difficult when the records are long and unstructured, and the potential queries are unconstrained. A good example of this occurs in directory assistance applications, where the database is the phonebook, and there are numerous ways for a customer to ask for a listing.
For example, if an entry for “3-L Hair World” (located on North 3rd Street) is in the database, a person might ask for it in many ways, e.g.                “3-L”        “Hair World”        “Hair World on 3rd Street”        
Further, the database might also include an entry for “Susie's Hair World” (located on Main Street). In this case, if a person asks for “Hair World” there is an ambiguity—no listing is uniquely identified.
In view of the foregoing, a need has been recognized in connection with facilitating database access in situations where such access might normally prove to be elusive or difficult.